package countQuadruplets;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    public int countQuadruplets(int[] nums) {
//        int [][]dp = new int[4][101];
//        dp[0][0] = 1;
//        int ans = 0;
//        for (int num: nums) {
//            for (int j = 3; j > 0; j--) {
//                for (int i = num; i <dp[0].length; i++) {
//                    dp[j][i] += dp[j-1][i-num];
//                }
//            }
//            ans += dp[3][num];
//        }
//        return ans;

        // 1--->哈希表
//        int n = nums.length,ans = 0;
//        Map<Integer,Integer> map = new HashMap<>();
//        map.put(nums[n-1],1);
//        // 当枚举 nums[a] + nums[b] + nums[c] = nums[d] 时
//        // 可以先把大于c的索引的元素存储到map中
//        for (int c = n-2; c >=2 ; c--) {
//            map.put(nums[c],map.getOrDefault(nums[c],0)+1);
//            for (int a = 0; a < c-1; a++) {
//                for (int b = a+1; b < c; b++) {
//                    ans+=map.getOrDefault(nums[a] + nums[b] + nums[c],0);
//                }
//            }
//        }
//        return ans;

        // 哈希表存储 nums[d] - nums[c] 并且d>c的数量
        // 如果包含 nums[d] - nums[c]
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length,ans = 0;
        for (int b = n-3; b >=1; b--) {
            // 把nums[d] - nums[c] 的值存储起来
            for (int d = b+2; d <n ; d++) {
                map.put(nums[d] - nums[b+1],map.getOrDefault(nums[d] - nums[b+1],0)+1);
            }
            for (int a = b-1; a >=0 ; a--) {
                ans += map.getOrDefault(nums[b] + nums[a],0);
            }
        }
        return ans;

        // 背包问题

    }
}
